package imooc_math.graph;

import java.util.Iterator;
import java.util.Vector;

public class SparseGraph implements Graph{ 
	public int n;//节点数
	public int m;//边数
	public boolean directed;
	public Vector[] g;
	public SparseGraph(int n,boolean directed){
		this.n = n;
		this.m = 0;
		this.directed = directed;
		g = new Vector[n];
		for(int i=0;i<n;i++){
			g[i] = new Vector<Integer>();
		}
	}
	public int V(){return n;}
	public int E(){return m;}
	public void addEdge(int v,int w){
		if(hasEdge(v,w)){
			return;
		}
		g[v].add(w);
		//自指的问题  Vector这个集合继承自List，所以可以允许重复的元素插入
		if(v!=w && !directed){
			g[w].add(v);
		}
		m++;
	}
	//这个操作时间复杂度较高
	public boolean hasEdge(int v,int w){
		
		for(int i=0;i<g[v].size();i++){
			if((int)g[v].elementAt(i) == w){
				return true;
			}
		}
		return false;
	}
	public Iterable adj(int v){
		return g[v];
	}
	
	public void show() {
		for(int i=0;i<n;i++){
			 System.out.print("vertex " + i + ":\t");
			for(int j=0;j<g[i].size();j++){
				System.out.print(g[i].elementAt(j));
			}
			System.out.println();
		}
	}



}
